﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Leetcode_Array.Script.StackAndQueue
{

    //================C# 没有双向队列 头疼
    class MaxInQueue
    {
        // ========================力扣239 滑动窗口最大值
        //给定一个整数数组nums，有一个大小为k的滑动窗口从数组的最左侧移动到最右侧
        //你只可以看到在滑动窗口内的k个数字。滑动窗口每次只向右移动一位
        //返回滑动窗口中的最大值
        public int[] MaxSlidingWindow(int[] nums, int k)
        {
            int[] result = new int[nums.Length - k +1];
            //单调队列
            DecreaseQueue queue = new DecreaseQueue();
            for(int i = 0;i<k;i++)
            {//先放入前k个元素到队列
                queue.Push(nums[i]);
            }
            result[0] = queue.Front();//放入前k个元素中的最大值

            for(int i = k;i<nums.Length;i++)
            {
                queue.Pop(nums[i - k]);//滑动窗口移除最前面的元素
                queue.Push(nums[i]);//滑动窗口前加入最后面的元素
                result[i - k + 1] = queue.Front();//放入当前最大值
            }
            return result;
        }
    }


    class DecreaseQueue
    {
        public Queue<int> que;

        public DecreaseQueue()
        {
            que = new Queue<int>();
        }

        //如果push的数值大于入口元素的数值，那么久将队列后端的数值弹出，直到push的数值小于等于队列入口元素的数值为止
        //这就保证了队列里的数值是单调递减的
        public void Push(int value)
        {
            while (que.Count > 0 && value > que.Peek())
            {
                que.Dequeue();
            }
            que.Enqueue(value);
        }

        //每次弹出时，比较要弹出的数值是否等于队列出口元素的数值，如果相等则弹出
        //同事pop之前判断当前队列是否为空
        public void Pop(int value)
        {
            if (que.Count > 0 && value == que.Peek())
                que.Dequeue();
        }

        //查询当前队列里的最大值，即是队列的前端
        public int Front()
        {
            return que.Peek();
        }
    }
}
